package dmsxl.lianbiao;

import java.util.HashMap;
import java.util.HashSet;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/9 21:26
 */
public class lb7_142 {

    public static void main(String[] args) {
        ListNode node = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);

        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node1;

        System.out.println(detectCycle(node).val);
    }

//    自己做的，加了hashset，效果一般
    public static ListNode detectCycle1(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        if (head == null) return null;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        while (true){
            if (dummyNode.next == null) return null;
            else if (dummyNode.next!=null && !set.contains(dummyNode.next)){
                set.add(dummyNode.next);
                dummyNode = dummyNode.next;
            }else if (dummyNode.next!=null && set.contains(dummyNode.next)){
                return dummyNode.next;
            }
        }
    }

//    双指针，想不到，效率高
    public static ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode fastPtr = head;
        ListNode slowPtr = head;
        boolean loopExists = false;
        while (fastPtr.next!=null && fastPtr.next.next!=null){
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
            if(fastPtr==slowPtr){
                loopExists = true;
                break;
            }
        }
        if(loopExists){
            slowPtr = head;
            while (slowPtr != fastPtr){
                fastPtr = fastPtr.next;
                slowPtr = slowPtr.next;
            }
            return slowPtr;
        }
        return null;
    }
}
